package l.l.w.practice.CoinCombination;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by llw on 2017/9/14.
 * 题目描述：
 *      现有一堆银币：1 1 2 2 4 4 8 8 ... (面值为2^k次方)，每个相同的硬币有两个，问钱币n有多少种组织方式？
 *      比如 输入 6， 组合方式有（1 1 2 2）（2 4）(1 1 4)3种
 */
public class CoinCombination {

    public static List<List<Integer>> getAllCombination(int n){
        HashSet<Integer> set = new HashSet<>();
        /*
         这个地方要考虑二进制。
         a+b=n,
          */
        for(int a = 0; a <= (n+1)/2;++a){
            int b = n-a;
            set.add(a|b);
        }
        //输出所有的情况
        List<List<Integer>> result = new LinkedList<>();
        Iterator<Integer> iterator = set.iterator();
        while(iterator.hasNext()){
            Integer k = iterator.next();
            LinkedList<Integer> list = new LinkedList<>();
            list.addAll(com(k));
            list.addAll(com(n-k));
            result.add(list);
        }
        return result;
    }


    public static List<Integer> com(int k){
        List<Integer> result = new LinkedList<>();
        while(k != 0){
            int p = k & (~k + 1);
            result.add(p);
            k=k-p;
        }
        return result;
    }
    public static void main(String[] args) {
        int a = 6;
        List<List<Integer>> result = CoinCombination.getAllCombination(a);
        System.out.println(result);
    }
}
